#include <iostream>
#include <UnidirectionLinkedList.hpp>
#include <vector>

using namespace std;

class Solution
{
public:
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        if (lists.empty())
            return nullptr;
        return mergeKLists(lists, 0, lists.size() - 1);
    }

    ListNode *mergeKLists(vector<ListNode *> &lists, int start, int end)
    {
        if (start == end)
            return lists[start];
        else
        {
            int mid = (start + end) / 2;
            return mergeTwoLists(mergeKLists(lists, start, mid), mergeKLists(lists, mid + 1, end));
        }
    }

    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
    {
        if (l1 == nullptr)
            return l2;
        if (l2 == nullptr)
            return l1;
        if (l1->val < l2->val)
        {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else
        {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

int main()
{
    cout << "Code23" << endl;
    Solution s;
    vector<ListNode *> lists;
    lists.push_back(CreateLinkedList(vector<int>{1, 4, 5}));
    lists.push_back(CreateLinkedList(vector<int>{1, 3, 4}));
    lists.push_back(CreateLinkedList(vector<int>{2,6}));
    PrintLinkedList(s.mergeKLists(lists));
    return 0;
}